﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.Intrinsics.Arm;
using System.Text;
using System.Threading.Tasks;
using static System.Net.Mime.MediaTypeNames;
class Sol322{

    public int CoinChange2(int[] coins, int amount)//动态规划,迭代法
    {//转移方程是dp（amout)=dp(amout-coin)+1
        //条件是这次选了哪个硬币
     
     int[] dp=new int[amount+1];
        for(int i=0; i< dp.Length; i++)
        {
            dp[i] = amount+1;
        }

        for (int i = 1; i <= amount; i++)
        {
            int min = amount;
            for (int j = 0; j < coins.Length; j++)
            {
                if(i - coins[j] < 0)//i - coins[j]是amount的目标，不可能小于0
                {
                   
                }
                else
                {
                    //找最小的  dp[i - coins[j]] 
                    if (dp[i - coins[j]] < min)
                    {
                        min = dp[i - coins[j]];//如果没有符合条件的，这个min不变，一直amou
                    }
                }

            }
            Console.WriteLine(min);
            dp[i] = min+1;//增加一枚

        }


        if (dp[amount] > amount)//说明没有符合的
        {
            return -1;
        }
        return dp[amount];
       





    }
    public int CoinChange3(int[] coins, int amount)//递归法,这个方法计算1的太多了，超时
    {
        if (amount == 0)
        {
            return 0;
        }
      int res=  myCoinChange(coins, amount);
        if(res> amount)
        {
            return -1;
        }
        return res;
    }


        public int myCoinChange(int[] coins, int amount)//递归法
    {
        Console.WriteLine("amount" + amount);
        int min = int.MaxValue;
        if (amount == 0)
        {
            return 0;//说明使用0枚硬币
        }

        //当前层选择的不一定是bigger，小于amout的里面最大的
        //所以每个情况都要考虑到

        
        for (int j = 0; j < coins.Length; j++)
        {

            if(amount >= coins[j])
            {
                int next = myCoinChange(coins, amount - coins[j]);//记录当前层的最小值，下一层的使用

               
                if (min > next)
                {
                    min = next;
                }
            }

            Console.WriteLine("min" + min);
        }
       

        
        return min+1;//本次使用了一枚


    }
    //递归法+记忆化搜索
    //遇到重复值会出问题
    public int CoinChange(int[] coins, int amount)//递归法,回溯？
    {
        if (amount == 0)
        {
            return 0;
        }
        int res = myCoinChange2(coins, amount, new int[amount]);
        if (res > amount)
        {
            return -1;
        }
        return res;
    }


    public int myCoinChange2(int[] coins, int amount, int[] count)//递归法,使用count记录某个金额的最小值
    {
        Console.WriteLine("amount" + amount);
        int min = int.MaxValue;//amount是变化的
        if(amount < 0) { return -1; }
        if (amount == 0)
        {
            return 0;//说明使用0枚硬币
        }

        if (count[amount-1] != 0)//说明计算过了
        {
            return count[amount - 1];
        }


        //当前层选择的不一定是bigger，小于amout的里面最大的
        //所以每个情况都要考虑到


        for (int j = 0; j < coins.Length; j++)
        {

            if (amount >= coins[j])
            {
                int next = myCoinChange2(coins, amount - coins[j], count);//记录后面的amount需要使用几个硬币


                if (next>=0&&min > next)
                {
                    min = next;//记录下一层的最小值
                }
            }

            Console.WriteLine("min" + min);
        }

        //记录一下count[amount - 1]
       
        if(min== int.MaxValue)//说明min没有变化，下一层不符合条件
        {
            count[amount - 1] = -1;
        }
        else
        {
            count[amount - 1] =min+1;
        }
        return count[amount - 1];//本次使用了一枚


    }

    int coinSum = 0;//正着算比较方便，方便回溯
    int coinNum= 0;//正着算比较方便，方便回溯
    int minNum;
    public int CoinChange7(int[] coins, int amount)//回溯？超时，而且边界条件比较多
    {

        minNum = amount + 2;
            DFS(0, coins, amount);
        if (minNum >amount)
        {
            return -1;
        }
        return minNum;
       

    }

    private void DFS(int start, int[] coins, int amount)
    {
        Console.WriteLine("coinNum"+coinNum);
        Console.WriteLine("coinSum" + coinSum);
        if (amount == coinSum)
        {
            minNum =Math.Min(minNum, coinNum);
            Console.WriteLine("minNum"+minNum);
            return;
        }
        if(amount< coinSum)
        {
            return;//超出了就返回
        }
        if (coinNum > amount)
        {
            return;
        }

        for (int j = 0; j < coins.Length; j++)
        {
            
            if (amount>=coins[j] )
            {
                coinNum++;
                coinSum += coins[j];
                DFS(j + 1, coins, amount);
                coinSum -= coins[j];
                coinNum--;
            }
           
        }

    }
    int[] visited;
    public int CoinChange8(int[] coins, int amount)//回溯？超时，优化
    {
        visited = new int[amount];
        minNum = amount + 2;
        DFS2(0, coins, amount);
        if (minNum > amount)
        {
            return -1;
        }
        return minNum;


    }

    private void DFS2(int start, int[] coins, int amount)
    {
        Console.WriteLine("coinNum" + coinNum);
        Console.WriteLine("coinSum" + coinSum);




        if (amount == coinSum)
        {
            minNum = Math.Min(minNum, coinNum);
            Console.WriteLine("minNum" + minNum);
            return;
        }
        if (amount < coinSum)
        {
            return;//超出了就返回
        }
        if (coinNum > amount)
        {
            return;
        }

        for (int j = 0; j < coins.Length; j++)
        {

            if (amount >= coins[j])
            {
                coinNum++;
                coinSum += coins[j];
                DFS2(j + 1, coins, amount);
                coinSum -= coins[j];
                coinNum--;
            }

        }

    }
}
class Program322
{

    static void Main322(string[] args)
    {

        //int[] balls = [1, 5, 2];
        //int amount = 100;

        int[] balls = [281, 20, 251,251];
        int amount = 7323;
        //int[] balls = [1];
        //int amount = 1;
        Sol322 sol = new Sol322();
        int res = sol.CoinChange(balls, amount);
        Console.WriteLine("res" + res);

    }
}